#include <stdio.h>
#include <malloc.h>
//二叉搜索树 BST binary search tree

//1.定义一个结构体
typedef int ElementType;
typedef struct node *BST;
struct node{
    //数据项
    ElementType data;
    //2.地址项，有两个指针，分别指向左右子结点
    struct node *left;
    struct node *right;
} ;

//插入函数
/*
 * 步骤：（1）找位置 通过对比
 *         1.1 如果传入的value>node.data ,在右子树插入
 *         1.2 如果传入的value<node.data,在左子树插入
 *      （2）插入
 *         2.1 创建结点
 *         2.2 赋值
 * */

/*
 * 函数名：insert()
 * 输入：空树,待插入的数值
 * 输出：返回创建好的树
 * */
BST insert(BST root,ElementType value){

    if(root==NULL){
        root =malloc(sizeof(struct node));
        root->data=value;
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    //找位置 ,找到位置插入
    if(value>root->data){
       root->right = insert(root->right,value);
    }
    if(value<root->data){
        root->left= insert(root->left,value);
    }
    return root;
}


//找最小值
/*
 * 对于BST树而言，最小值存放在树的最左端的结点里。
 * 定义一个指针 node
 *  循环{
 *      node=node.left;
 * }
 *
 * 指针不断往左移动，直到最左端，此时结点里面的值为最小值
 *   binary tree 二叉树  binary search tree
 *   BT BST
 *   AVL树
 *
 * 函数名：findmin()
 * 输入：树（根结点）
 * 输出：返回包含最小值的结点 BST
 * */
//BST root   ===  struct node *root
BST findMin(BST root ){
    //树为空
    if(root ==NULL)
        return NULL;
    //树不为空，执行搜索
    BST node = root;//设置一个指针，指针从根结点开始出发
    //指针不断的向左移动，直到最左端
    while(node->left!=NULL)
    {
        node =node->left;
    }
    return node;
}


BST findMax(BST root ){
    //树为空
    if(root ==NULL)
        return NULL;
    //树不为空，执行搜索
    BST node = root;//设置一个指针，指针从根结点开始出发
    //指针不断的向左移动，直到最左端
    while(node->right!=NULL)
    {
        node =node->right;
    }
    return node;
}
/*
 * 找特定值的结点，如存在返回该结点，不存在返回NULL
 * 方法：设传入的值为value,当前搜索范围内的树的根为node
 * 两者进行比较：
 * value >node  继续在node的右子树里进行查找
 * value <node  继续在node的左子树里进行查找
 * value == node  找到，返回该结点
 * node == NULL 没找到 ，返回NULL
 * */
/*
 * 函数名：findNode()
 * 输入：树，待查找值
 * 输出：存在 返回结点 不存在 返回NULL
 * */
BST findNode(BST root,ElementType value){
    //设置一个指针，指向当前比较范围内树的根结点
    BST node =root;
  /* if(node ==NULL)
        return NULL;*/
    while(node){
        if(value > node->data)
            node =node->right;
        else if(value<node->data)
            node =node->left;
        else
            return node;
    }
    return node;
}

int main() {
    BST bst =NULL;
    bst = insert(bst,4);
    bst = insert(bst,5);
    bst = insert(bst,8);
    bst = insert(bst,9);
    bst = insert(bst,12);
    BST minNode = findMin(bst);
    printf("最小值是%d\n",minNode->data);
    BST maxNode = findMax(bst);
    printf("最大值是%d\n",maxNode->data);
    int value =8;
    BST tmp = findNode(bst,value);
    if(tmp){
        printf("结点%d存在\n",value);
    } else{
        printf("结点%d不存在\n",value);
    }
    //printf("Hello, World!\n");
    return 0;
}




